package org.xingole.algo.dp;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * A Dynamic Programming based solution for the 0-1 Knapsack problem.
 * This class provides a method, {@code knapsack}, that calculate the
 * maximum value that can be obtained from a given set of items with
 * weights and values, while not exceeding a given weight capacity.
 * 
 * @see <a href="https://en.wikipedia.org/?title=0-1_Knapsack_problem">0-1 Knapsack Problem</a>
 */
public class Knapsack {

    private Knapsack() {

    }

    private static void throwIfInvalidInput(
        final int weightCapacity, 
        final int[] weigths, 
        final int[] values
    ) {
        if (weightCapacity < 0) {
            throw new IllegalArgumentException("Weigth capacity should not be negative.");
        }
        if (weigths == null || values == null || weigths.length != values.length) {
            throw new IllegalArgumentException("Input arrays must not be null and must have the same length.");
        }
        if (Arrays.stream(weigths).anyMatch(w -> w <= 0)) {
            throw new IllegalArgumentException("Input array should not contain non-positive weight(s).");
        }
    } 

    /**
     * Solves the 0-1 knapsack problem using Dynamic Programming.
     * 
     * @param weightCapacity The maximum weight capacity of the knapsack.
     * @param weights        An array of item weights.
     * @param values         An array of item values.
     * @return The maximum value that can obtained without exceeding the weight capacity.
     * @throws IllegalArgumentException If the input arrays are null or have different lengths.
     */
    public static int knapSack(
        final int   weightCapacity,
        final int[] weights,
        final int[] values
    ) throws IllegalArgumentException {
        throwIfInvalidInput(weightCapacity, weights, values);

        // DP table to store the state of the maximum possible return for a given weight capacity.
        int[] dp = new int[weightCapacity + 1];

        for (int i = 0; i < values.length; i++) {
            for (int w = weightCapacity; w > 0; w--) {
                if (weights[i] <= w) {
                    dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
                }
            }
        }

        return dp[weightCapacity];
    }

    /**
     * 
     * @param capacity The maximum capacity of the knapsack
     * @param W The weights of the items
     * @param V The values of the items
     * @return  The maximum achievable profit of selecting a subset of the elements such that the
     * capacity of the knapsack is not exceeded 
     */
    public static int knapsack(int capacity, int[] W, int[] V) {
        if (W == null || V == null || W.length != V.length || capacity < 0)
            throw new IllegalArgumentException("Invalid input");

        final int N = W.length;

        // Initialize a table where individual rows represent items
        // and columns represent the weight of the knapsack
        int[][] DP = new int[N + 1][capacity + 1];

        for (int i = 1; i <= N; i++) {

            // Get the value and weight of the item
            int w = W[i - 1], v = V[i - 1];

            for (int sz = 1; sz <= capacity; sz++) {

                // Consider not picking this element
                DP[i][sz] = DP[i - 1][sz];

                // Consider including the current element and
                // see if this would be more profitable
                if (sz >= w && DP[i - 1][sz - w] + v > DP[i][sz]) DP[i][sz] = DP[i - 1][sz - w] + v;
            }
        }

        int sz = capacity;
        List<Integer> itemsSelected = new ArrayList<>();

        // Using the information inside the table we can backtrack and determine
        // which items were selected during the dynamic programming phase. The idea
        // is that if DP[i][sz] != DP[i-1][sz] then the item was selected
        for (int i = N; i > 0; i--) {
            if (DP[i][sz] != DP[i - 1][sz]) {
                int itemIndex = i - 1;
                itemsSelected.add(itemIndex);
                sz -= W[itemIndex];
            }
        }

        // Return the items that were selected
        // java.util.Collections.reverse(itemsSelected);
        // return itemsSelected;

        // Return the maximum profit
        return DP[N][capacity];
    }
}
